Papers with quadratic complexity
Efficient Long-Text Understanding with Short-Text Models (2023.tacl-1)
Copied to clipboard
| Challenge: | Existing transformer-based pretrained language models cannot be applied to long sequences due to their quadratic complexity. |
| Approach: | They propose a simple approach to long sequences that re-uses battle-tested short-text pretrained LMs. |
| Outcome: | The proposed approach is competitive with specialized models that are up to 50x larger and require a dedicated and expensive pretraining step. |
Filtered Semi-Markov CRF (2023.findings-emnlp)
Copied to clipboard
| Challenge: | Existing methods for sequence labeling tasks such as Named Entity Recognition (NER) suffer from quadratic complexity over sequence length and poor performance compared to CRF. |
| Approach: | They propose a variant of Semi-Markov CRF that incorporates a filtering step to eliminate irrelevant segments, reducing complexity and search space. |
| Outcome: | The proposed method outperforms both CRF and Semi-CRF on several NER benchmarks while being significantly faster. |
Long-range Sequence Modeling with Predictable Sparse Attention (2022.acl-long)
Copied to clipboard
| Challenge: | Existing approaches to capture global context dependencies in sequence modeling suffer from quadratic complexity in time and memory usage. |
| Approach: | They propose an efficient Transformer architecture for fast long-range sequence modeling with a sparse attention matrix and a hidden state cross module. |
| Outcome: | The proposed architecture outperforms the standard multi-head attention and its variants in various long-sequence tasks with low computational costs. |
EdgeInfinite: A Memory-Efficient Infinite-Context Transformer for Edge Devices (2025.acl-industry)
Copied to clipboard
| Challenge: | Existing KV cache optimizations struggle with irreversible token eviction in long-output tasks . alternative sequence modeling architectures prove costly to adopt within established Transformer infrastructures. |
| Approach: | They propose a memory-efficient solution for infinite contexts that integrates compressed memory into Transformer-based LLMs through a trainable memory-gating module. |
| Outcome: | The proposed solution achieves comparable performance to baseline Transformer-based LLMs while optimizing memory consumption and time to first token. |
Long Document Summarization with Top-down and Bottom-up Inference (2023.findings-eacl)
Copied to clipboard
| Challenge: | Recent models infer latent representations of words or tokens with a transformer encoder, which is bottom-up and thus does not capture long-distance context well. |
| Approach: | They propose a method to infer latent representations of words or tokens in documents . they assume a hierarchical structure of a document where top-level captures long range dependency . |
| Outcome: | The proposed model can summarize an entire book and achieve competitive performance on a wide range of document summarization benchmarks. |
Video Compression Commander: Plug-and-Play Inference Acceleration for Video Large Language Models (2025.emnlp-main)
Copied to clipboard
| Challenge: | Recent studies have shown that Video Large Language Models (Vide-oLLMs) are efficient at video understanding but lack the quadratic complexity of visual tokens. |
| Approach: | They propose a plug-and-play inference acceleration framework for VideoLLM token compression that quantifies each frame’s uniqueness and adaptively adjusts compression intensity across frames. |
| Outcome: | Extensive experiments on video large language models and benchmarks show that the proposed framework can preserve essential information while reducing redundancy in video sequences. |
Hi-Transformer: Hierarchical Interactive Transformer for Efficient and Effective Long Document Modeling (2021.acl-short)
Copied to clipboard
| Challenge: | Existing approaches to model long documents are difficult due to the quadratic complexity of text length. |
| Approach: | They propose a hierarchical interactive Transformer for efficient long document modeling. |
| Outcome: | Extensive experiments on three benchmark datasets validate the efficiency and effectiveness of Hi-Transformer in long document modeling. |
Speechformer: Reducing Information Loss in Direct Speech Translation (2021.emnlp-main)
Copied to clipboard
| Challenge: | Current approaches to speech-to-text translation (ST) use a pipeline of two sub-components - an automatic speech recognition (ASR) and a machine translation (MT) model. |
| Approach: | They propose an architecture that avoids initial lossy compression and aggregates information only at a higher level according to more informed linguistic criteria. |
| Outcome: | The proposed architecture achieves gains of up to 0.8 BLEU on the standard MuST-C corpus and up to 4.0 BLUE in a low resource scenario. |
In-Context Former: Lightning-fast Compressing Context for Large Language Model (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Existing methods to reduce inference costs of transformer-based large language models entail quadratic complexity . et al., 2017): transformer-derived large language model performance is a major challenge. |
| Approach: | They propose a method that compresses long contexts into short soft prompts . they use the self-attention mechanism of the large model to extract and condense information . |
| Outcome: | The proposed method reduces compression costs by 68 to 112 times while achieving 90% of baseline performance. |
Enhancing Long-range Dependency with State Space Model and Kolmogorov-Arnold Networks for Aspect-based Sentiment Analysis (2025.coling-main)
Copied to clipboard
| Challenge: | Aspect-based Sentiment Analysis (ABSA) evaluates sentiments toward specific aspects of entities within the text. |
| Approach: | They propose a method to enhance long-range dependencies between aspect and opinion words in ABSA by combining attention mechanisms with a syntax-based Graph Convolutional Network and a Mamba-Transformer module. |
| Outcome: | The proposed model outperforms state-of-the-art models on three benchmark datasets. |
Multimodal Phased Transformer for Sentiment Analysis (2021.emnlp-main)
Copied to clipboard
| Challenge: | Existing methods to model multimodal sentiment analysis are limited due to their complexity and memory footprint. |
| Approach: | They propose a multimodal Sparse Phased Transformer to reduce self-attention complexity and memory footprint. |
| Outcome: | The proposed method achieves comparable or superior performance with a 90% reduction in the number of parameters. |
LM-Infinite: Zero-Shot Extreme Length Generalization for Large Language Models (2024.naacl-long)
Copied to clipboard
| Challenge: | Currently, large language models (LLMs) train on short text segments due to the computational overhead quadratic in the input lengths of their Transformer architectures. |
| Approach: | They propose a method that allows LLMs pre-trained with 2K or 4K-long segments to generalize to up to 200M length inputs while retaining perplexity. |
| Outcome: | The proposed method achieves 2.7 decoding speed up and 7.5 memory saving over the original model. |
DAM: Dynamic Attention Mask for Long-Context Large Language Model Inference Acceleration (2025.findings-acl)
Copied to clipboard
| Challenge: | Long-context understanding is crucial for many NLP applications, but transformers struggle with efficiency due to quadratic complexity of self-attention. |
| Approach: | They propose a dynamic sparse attention mechanism that assigns adaptive masks at the attention-map level, preserving heterogeneous attention patterns. |
| Outcome: | The proposed method achieves high alignment with full-attention models while reducing memory and compute overhead. |
A Survey of Retentive Network (2026.findings-acl)
Copied to clipboard
| Challenge: | Existing studies on the effectiveness of the Retentive Networks have not yet been conducted. |
| Approach: | They propose a retention mechanism that integrates the inductive bias of recurrent neural networks with the parallelizable training advantages of attention-based models. |
| Outcome: | The proposed retention mechanism combines the inductive bias of recurrent neural networks with the parallelizable training advantages of attention-based models. |
Extending Context Window of Large Language Models via Semantic Compression (2024.findings-acl)
Copied to clipboard
| Challenge: | Existing models rely on a quadratic computation to generate long texts . current models impose limitations on the length of text inputs . |
| Approach: | They propose a semantic compression method that extends the context window of large language models . the method reduces the semantic redundancy of long inputs before passing them to the LLMs . |
| Outcome: | The proposed method extends the context window of large language models across tasks . it exhibits consistent fluency in text generation while reducing associated computational overhead. |
MoPrune: Scene-Guided Motion-Aware Token Pruning for Efficient Video Large Language Models (2026.findings-acl)
Copied to clipboard
| Challenge: | Prior approaches to token pruning ignore video dynamics and the fact that different scenes exhibit different redundancy patterns. |
| Approach: | They propose a token pruning framework that is train-free and scene-guided to accelerate VideoLLMs by removing redundant visual information from video frames. |
| Outcome: | MoPrune is a training-free, scene-guided and motion-centric token pruning framework for accelerating VideoLLMs. |
LycheeCluster: Efficient Long-Context Inference with Structure-Aware Chunking and Hierarchical KV Indexing (2026.findings-acl)
Copied to clipboard
| Challenge: | Existing retrieval-based methods compromise semantic integrity through fixed-size chunking and suffer from inefficient linear scanning. |
| Approach: | They propose a method that preserves local semantic coherence through boundary-aware chunking and constructs a recursive hierarchical index rooted in the triangle inequality. |
| Outcome: | The proposed method achieves 3.6 end-to-end inference speedup with negligible degradation in model performance. |
Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences (2022.naacl-main)
Copied to clipboard
| Challenge: | Existing models for long sequences are not efficient due to the quadratic space and time complexity of the self-attention modules. |
| Approach: | They propose to reduce the quadratic complexity to linear (modulo logarithmic factors) by low-dimensional projection and row selection. |
| Outcome: | The proposed methods outperform transformer-based models with smaller time/space footprint on the Long Range Arena benchmark. |
AnchorAttention: Difference-Aware Sparse Attention with Stripe Granularity (2025.emnlp-main)
Copied to clipboard
| Challenge: | Existing methods for large language models with extended context lengths face significant computational challenges during the prefill phase. |
| Approach: | They propose a difference-aware, dynamic sparse attention mechanism that efficiently identifies critical attention regions at a finer stripe granularity while adapting to global contextual information. |
| Outcome: | The proposed model achieves a speedup of 1.44 while maintaining higher recall rates. |
Language-Guided Temporal Token Pruning for Efficient VideoLLM Processing (2025.emnlp-main)
Copied to clipboard
| Challenge: | Current models struggle with long-form videos due to the quadratic complexity of attention mechanisms. |
| Approach: | They propose a model-agnostic framework that leverages temporal cues from queries to prune video tokens. |
| Outcome: | The proposed framework reduces computation by 65% while preserving 97-99% of original performance. |
ABC: Attention with Bounded-memory Control (2022.acl-long)
Copied to clipboard
Hao Peng, Jungo Kasai, Nikolaos Pappas, Dani Yogatama, Zhaofeng Wu, Lingpeng Kong, Roy Schwartz, Noah A. Smith
| Challenge: | Existing approaches to attention with bounded-memory control (ABC) have a quadratic complexity in sequence lengths, making it prohibitive for long sequences. |
| Approach: | They propose a new abstraction that bounds memory size to improve efficiency . they propose bounded-memory control, which connects several efficient attention variants . |
| Outcome: | The proposed approach outperforms existing approaches on language modeling, machine translation, and masked language model finetuning. |
Revealing and Mitigating the Local Pattern Shortcuts of Mamba (2025.findings-acl)
Copied to clipboard
| Challenge: | Recent studies show that Mamba excels in tasks that involve localized key information but faces challenges with tasks that require handling distributed key information. |
| Approach: | They propose to introduce a global gate module into Mamba to address this problem by adding 4M extra parameters to the model. |
| Outcome: | The proposed model outperforms attention-based models on synthetic and synthetic tasks with only 4M extra parameters. |
How Do Hyenas Deal with Human Speech? Speech Recognition and Translation with ConfHyena (2024.lrec-main)
Copied to clipboard
| Challenge: | Currently, attention-based models face computational hurdles in processing long sequences due to its quadratic complexity. |
| Approach: | They propose a conformer whose encoder self-attentions are replaced with Hyena for speech processing . they propose 'confhyena' model that reduces training time by 27% at minimal cost . |
| Outcome: | The proposed model reduces training time by 27% at the cost of minimal quality degradation. |
PuMer: Pruning and Merging Tokens for Efficient Vision Language Models (2023.acl-long)
Copied to clipboard
| Challenge: | Large-scale vision language models use Transformers to perform cross-modal interactions . state-of-the-art models are memory intensive and expensive due to quadratic complexity . |
| Approach: | They propose a token reduction framework that uses text-informed Pruning and modality-aware Merging strategies to progressively reduce the tokens of input image and text. |
| Outcome: | The proposed framework improves inference speed and memory footprint on four vision language tasks. |
Value-aware Approximate Attention (2021.emnlp-main)
Copied to clipboard
| Challenge: | Existing approximations of dot-product attention ignore the value vectors . a value-aware objective outperforms an optimal approximate that ignores values . |
| Approach: | They propose an approximation of a value-aware objective that substantially outperforms an optimal approximate that ignores values. |
| Outcome: | The proposed value-aware objective outperforms an optimal approximation that ignores values in the context of language modeling. |
Context Compression for Auto-regressive Transformers with Sentinel Tokens (2023.emnlp-main)
Copied to clipboard
| Challenge: | Existing Transformer-based LLMs have limited performance due to complexity of attention module . key-value cache is the major memory footprint and inference latency problem . |
| Approach: | They propose a plug-and-play approach that incrementally compresses token activation into compact ones . they also profile the benefit of context compression on improving the system throughout . |
| Outcome: | The proposed approach reduces memory footprint and inference latency by compressing tokens into compact ones. |
Query-based Cross-Modal Projector Bolstering Mamba Multimodal LLM (2024.findings-emnlp)
Copied to clipboard
| Challenge: | Existing models that capture multiple modalities with a single input length are unable to handle this computational burden. |
| Approach: | They propose a query-based cross-modal projector that compresses visual tokens based on input through the cross-attention mechanism. |
| Outcome: | The proposed projector reduces the need for manually designing the 2D scan order of original image features when converting them into an input sequence for Mamba LLMs. |
HyperMixer: An MLP-based Low Cost Alternative to Transformers (2023.acl-long)
Copied to clipboard
Florian Mai, Arnaud Pannatier, Fabio Fehr, Haolin Chen, Francois Marelli, Francois Fleuret, James Henderson
| Challenge: | Existing MLP-based architectures that combine multiple features are expensive and require a lot of training data. |
| Approach: | They propose a simple MLP-based model which allows token mixing by dynamically applying hypernetworks to each feature independently. |
| Outcome: | The proposed model performs better than Transformers and lowers costs in terms of processing time, training data, and hyperparameter tuning. |
Sparsifying Mamba (2025.findings-emnlp)
Copied to clipboard
| Challenge: | Existing attempts to integrate sparsification with Mamba fail to leverage Mamba's internal structure for fine-grained sparsifying. |
| Approach: | They propose to use Mamba to integrate sparsification into Mamba and propose a flexible and effective mechanism for parameter scalability. |
| Outcome: | The proposed framework can independently achieve parameter scalability and has stronger performance. |
Mamba Drafters for Speculative Decoding (2025.findings-emnlp)
Copied to clipboard
Daewon Choi, Seunghyuk Oh, Saket Dingliwal, Jihoon Tack, Kyuyoung Kim, Woomin Song, Seojin Kim, Insu Han, Jinwoo Shin, Aram Galstyan, Shubham Katiyar, Sravan Babu Bodapati
| Challenge: | Existing drafters that use external drafters suffer from slower drafting while self-speculation methods use drafters tailored to the target model but require re-training. |
| Approach: | They propose a drafter based on a state space model, Mamba, as a solution that combines the best aspects of both approaches. |
| Outcome: | The proposed drafters outperform existing drafters while using less memory and maintaining their cross-model adaptability. |
Latent-Condensed Transformer for Efficient Long Context Modeling (2026.acl-long)
Copied to clipboard
| Challenge: | Existing approaches address these bottlenecks separately: Multi-head Latent Attention (MLA) reduces the KV cache by projecting tokens into a low-dimensional latent space, while sparse attention reduces computation. |
| Approach: | They propose a Latent-Condensed Attention mechanism that performs structured context condensation directly within MLA's latent space. |
| Outcome: | The proposed approach reduces KV cache size and attention cost without adding parameters. |
From Logical to Computational Sparsity: Structure-Aware Block-Sparse Attention for Long-Code Completion (2026.acl-long)
Copied to clipboard
| Challenge: | Existing sparse attention methods for long-context generation pose high latency . general sparsity methods cause excessive accuracy degradation without considering code structure . |
| Approach: | They propose a training-free **S**tructure-**a**ware **b**lock-spa**r**s**e** attention mechanism that bridges the gap between logical and computational sparsity. |
| Outcome: | The proposed method reduces TTFT by 45-55% while maintaining accuracy within 3% of dense attention. |
RRAtention: Dynamic Block Sparse Attention via Per-Head Round-Robin Shifts for Long-Context Inference (2026.acl-long)
Copied to clipboard
Siran Liu, Guoxia Wang, Sa Wang, Jinle Zeng, Haoyang Xie, Siyu Lou, Jiabin Yang, Dianhai Yu, Haifeng Wang, Chao Yang
| Challenge: | Existing approaches to dynamic sparse attention require preprocessing, lack global evaluation, violate query independence, or incur high computational overhead. |
| Approach: | They propose a dynamic sparse attention method that achieves all desirable properties through a head **r**ound-**r**obin (RR) sampling strategy. |
| Outcome: | Experiments on natural language understanding and multimodal video comprehension show that the proposed method achieves 2.4 speedup at 128K context length outperforming existing methods. |
Tackling Long Code Search with Splitting, Encoding, and Aggregating (2024.lrec-main)
Copied to clipboard
| Challenge: | Existing pretraining models take the first 256 tokens of code snippets by default, limiting the input length to 512. |
| Approach: | They propose a baseline SEA model which splits long code into code blocks and aggregates them to obtain a comprehensive long code representation. |
| Outcome: | The proposed model can model long code without changing their internal structure and re-pretraining. |
Lizard: An Efficient Linearization Framework for Large Language Models (2026.acl-long)
Copied to clipboard
Chien Van Nguyen, Huy Huu Nguyen, Ruiyi Zhang, Hanieh Deilamsalehy, Puneet Mathur, Viet Dac Lai, Haoliang Wang, Jayakumar Subramanian, Ryan A. Rossi, Trung Bui, Nikos Vlassis, Franck Dernoncourt, Thien Huu Nguyen
| Challenge: | Existing linearization frameworks that rely on softmax attention with quadratic time and memory complexity pose significant computational and memory bottlenecks for long-context applications. |
| Approach: | They propose a linearization framework that transforms pretrained Transformer-based Large Language Models into subquadratic architectures that closely approximate softmax attention while preserving model quality. |
| Outcome: | Experiments show that the proposed framework outperforms existing methods by 9.4 - 24.5 points on the 5-shot MMLU benchmark and demonstrating superior associative recall. |
CoMeT: Collaborative Memory Transformer for Efficient Long Context Modeling (2026.acl-long)
Copied to clipboard
Runsong Zhao, Shilei Liu, Jiwei Tang, Langming Liu, Haibin Chen, Weidong Zhang, Yujin Yuan, Tong Xiao, JingBo Zhu, Wenbo Su, Bo Zheng
| Challenge: | a novel architecture that enables LLMs to handle arbitrarily long sequences with constant memory usage and linear time complexity is a major barrier to long-context processing. |
| Approach: | They propose a novel architecture that enables LLMs to handle arbitrarily long sequences with constant memory usage and linear time complexity. |
| Outcome: | The proposed architecture can handle arbitrarily long sequences with constant memory usage and linear time complexity. |